package com.javabasic.algorithm.leetcode;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/1 15:29
 * @Version 1.0
 * @题解：https://leetcode-cn.com/problems/combination-sum/comments/
 **/
public class CombinationSum {

    /**
     * 递归解法
     */
    public List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        getResult(0,0,candidates,target,new ArrayList<Integer>());
        return result;
    }

    private void getResult(int index, int sum, int[] candidates, int target, ArrayList<Integer> list) {
        if (sum > target) return;
        if (sum == target) {
            result.add(new ArrayList<>(list));
            return;
        }
        if (index >= candidates.length) return;

        // 不选取当前元素，之后也都不选取，所以index +1
        getResult(index+1,sum,candidates,target,list);
        list.add(candidates[index]);

        // 选取当前元素，由于当前元素可重复选取所以index不改变
        getResult(index,sum+candidates[index],candidates,target,list);
        list.remove(list.size()-1);
    }
}
